package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-13 10:50
 */
public class maxNum {
    public static void main(String[] args) {
        System.out.println(askMaxNum(10));
    }

    /**LeetCode 343
     * 五部曲：1.数组下标以及其含义：i代表将数字i所拆分的最大整数dp[i]代表将i拆分的最大整数2.递推公式：dp[i]=max(j*(i-j),j*dp[i-j])
     * 3.初始化:dp[0]=0;dp[1]=0,dp[2]=1;对0和1拆分本身没有意义4.遍历顺序：后面的值都是前面的值推出来的，所以遍历顺序是从前往后
     * @param n
     * @return
     */
    public static int askMaxNum(int n){
        //创建dp数组
        int[]dp=new int[n+1];
        //从前开始，不断往后遍历当前i所能生成的最大值
        for(int i=3;i<=n;++i){
            for(int j=1;j<i;++j){
                dp[i]=Math.max(dp[i],Math.max(j*(i-j), j*dp[i-j]));
            }
        }
        return dp[n];
    }
}
